public class Solution1977 {

    public int numberOfCombinations(String num) {
        if (num.startsWith("0")){
            return 0;
        }
        int mod=1000000007;
        int[][] prev=new int[num.length()][num.length()+1];
        for (int i=0;i<num.length();i++){
            int[] f=new int[num.length()];
            f[0]=1;
            for (int j=1;j<=i;j++){
                if (num.charAt(j)=='0'){
                    f[j]=0;
                    continue;
                }
                int start=Math.max(0,2*j-i);
                if (2*j-i-1>=0 && num.substring(2*j-i-1,j).compareTo(num.substring(j,i+1))<=0){
                    start=2*j-i-1;
                }
                f[j]=((prev[j-1][j]-prev[j-1][start])%mod+mod)%mod;

            }
            for (int j=1;j<=i+1;j++){
                prev[i][j]=(prev[i][j-1]+f[j-1])%mod;
            }
        }
        return prev[num.length()-1][num.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1977().numberOfCombinations("9999999999999"));
    }
}
